package leetcode_5000;

import java.util.HashMap;
import java.util.Map;

public class _最小化舍入误差以满足目标 {
	public static void main(String[] args) {
		_最小化舍入误差以满足目标 test = new _最小化舍入误差以满足目标();
		System.out.println(test.minimizeError(new String[] {"0.700","2.800","4.900"}, 8));
	}
	
	public String minimizeError(String[] prices, int target) {
        Map<Double,Double> dp = new HashMap<Double,Double>();
        double val = Double.parseDouble(prices[0]);
        double floor = Math.floor(val);
        double ceil = Math.ceil(val);
        dp.put(floor,val-floor);
        dp.put(ceil,ceil-val);
        for(int i=1;i<prices.length;++i) {
        	val = Double.parseDouble(prices[i]);//当前的值
        	floor = Math.floor(val);
        	ceil = Math.ceil(val);
        	 Map<Double,Double> now = new HashMap<Double,Double>();
        	 for(Double key:dp.keySet()) { 
        		 double preV = dp.get(key);//之前的val 最优解
        		 double d = key+floor; //现在的值
        		 now.put(d,Math.min(now.getOrDefault(d, Double.MAX_VALUE), preV+val-floor));
        		 d = key+ceil;
        		 now.put(d,Math.min(now.getOrDefault(d, Double.MAX_VALUE), preV+ceil-val));
        	 }
        	 dp = now;
        }
        double d = (double)target;
        if(!dp.containsKey(d)) return "-1";
        return String.format("%.3f",dp.get(d));
    }
}
